package backTracking;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

//131. 分割回文串
public class Num131_partition {
    List<List<String>>lists = new ArrayList<>();
    Deque<String>deque = new LinkedList<>();
    public List<List<String>> partition(String s) {
        backTracking(s , 0);
        return lists;
    }
    private void backTracking(String s , int startIndex){
        if (startIndex >= s.length()){
            lists.add(new LinkedList<>(deque));
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            if (isPalindrome(s , startIndex , i)){
                String str = s.substring(startIndex , i + 1);
                deque.addLast(str);
            }else {
                continue;
            }
            backTracking(s , i + 1);
            deque.removeLast();
        }


    }
    private boolean isPalindrome(String s , int l , int r){
        while (l < r){
            if (s.charAt(l) != s.charAt(r))return false;
            l++;
            r--;
        }
        return true;
    }
}
